import collections


class Solution(object):
    def pyramidTransition(self, bottom, allowed):
        """
        :type bottom: str
        :type allowed: List[str]
        :rtype: bool
        """
        a_dict = collections.defaultdict(set)
        for t in allowed:
            a_dict[t[:2]].add(t[2])

        def find_next(layer, i, n, next_layer):
            if a_dict[layer[i] + layer[i + 1]]:
                for next_point in a_dict[layer[i] + layer[i + 1]]:
                    next_layer.append(next_point)
                    if i == n - 2:
                        flag = search(next_layer)
                    else:
                        flag = find_next(layer, i + 1, n, next_layer)
                    if flag:
                        return True
                    next_layer.pop()
                return False
            else:
                return False

        def search(layer):
            next_layer = []
            n = len(layer)
            if n == 1:
                return True
            else:
                return find_next(layer, 0, n, next_layer)

        first = list(bottom)
        return search(first)

data = Solution()
bottom = "BCD"
allowed = ["BCC", "CDE", "CEA", "FFF"]
print(data.pyramidTransition(bottom, allowed))
bottom = "AABA"
allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
print(data.pyramidTransition(bottom, allowed))